package com.peng.leetcode.search;

/**
 * SearchRange
 * <p>
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 *
 * @author: lupeng6
 * @create: 2021/4/21 10:28
 */
public class SearchRange {

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int[] ints = new SearchRange().searchRange(nums, 8);
        System.out.println(ints);
    }


    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        ans[0] = search(nums, target, true);
        ans[1] = search(nums, target, false);
        return ans;
    }

    public int search(int[] nums, int target, boolean searchLower) {
        int len = nums.length;
        int l = 0;
        int r = len - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int midVal = nums[mid];

            if (midVal == target) {
                if (searchLower) {
                    if (mid == 0 || nums[mid - 1] != target) {
                        return mid;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    if (mid == len - 1 || nums[mid + 1] != target) {
                        return mid;
                    } else {
                        l = mid + 1;
                    }
                }
            } else if (midVal > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return -1;
    }
}
